{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest Component Size by Common Factor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #union-find #array #hash-table #math #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #并查集 #数组 #哈希表 #数学 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestComponentSize"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #按公因数计算最大组件大小"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个由不同正整数的组成的非空数组&nbsp;<code>nums</code> ，考虑下面的图：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>有&nbsp;<code>nums.length</code>&nbsp;个节点，按从&nbsp;<code>nums[0]</code>&nbsp;到&nbsp;<code>nums[nums.length - 1]</code>&nbsp;标记；</li>\n",
    "\t<li>只有当&nbsp;<code>nums[i]</code>&nbsp;和&nbsp;<code>nums[j]</code>&nbsp;共用一个大于 1 的公因数时，<code>nums[i]</code>&nbsp;和&nbsp;<code>nums[j]</code>之间才有一条边。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回 <em>图中最大连通组件的大小</em> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2018/12/01/ex1.png\" style=\"height: 97px; width: 500px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,6,15,35]\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2018/12/01/ex2.png\" style=\"height: 85px; width: 500px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [20,50,9,63]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2018/12/01/ex3.png\" style=\"height: 260px; width: 500px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,3,6,7,4,12,21,39]\n",
    "<strong>输出：</strong>8\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>nums</code>&nbsp;中所有值都 <strong>不同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-component-size-by-common-factor](https://leetcode.cn/problems/largest-component-size-by-common-factor/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-component-size-by-common-factor](https://leetcode.cn/problems/largest-component-size-by-common-factor/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,6,15,35]', '[20,50,9,63]', '[2,3,6,7,4,12,21,39]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        factors = []\n",
    "        for num in nums:\n",
    "            fac = []\n",
    "            p = 2\n",
    "            while p * p <= num:\n",
    "                if num % p == 0:\n",
    "                    while num % p == 0:\n",
    "                        num //= p      \n",
    "                    fac.append(p)\n",
    "                p += 1 \n",
    "            if not fac or num > 1:\n",
    "                fac.append(num)\n",
    "            factors.append(fac)\n",
    "        primes = sorted(set(p for fac in factors for p in fac))\n",
    "        index = {p : i for i, p in enumerate(primes)}\n",
    "        parent = {i : i for i in range(len(primes))}\n",
    "        def find(node):\n",
    "            path = []\n",
    "            while node != parent[node]:\n",
    "                path.append(node)\n",
    "                node = parent[node]\n",
    "            for p in path:\n",
    "                parent[p] = node\n",
    "            return node\n",
    "        \n",
    "        def union(n1, n2):\n",
    "            p1 = find(n1)\n",
    "            p2 = find(n2)\n",
    "            if p1 != p2:\n",
    "                parent[p1] = p2 \n",
    "        counter = collections.Counter()\n",
    "        for fac in factors:\n",
    "            for p in fac[1:]:\n",
    "                union(index[p], index[fac[0]])\n",
    "        for fac in factors:\n",
    "            counter[find(index[fac[0]])] += 1 \n",
    "        return counter.most_common(1)[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        factors = []\n",
    "        for num in nums:\n",
    "            fac = []\n",
    "            p = 2\n",
    "            while p * p <= num:\n",
    "                if num % p == 0:\n",
    "                    while num % p == 0:\n",
    "                        num //= p      \n",
    "                    fac.append(p)\n",
    "                p += 1 \n",
    "            if not fac or num > 1:\n",
    "                fac.append(num)\n",
    "            factors.append(fac)\n",
    "        primes = sorted(set(p for fac in factors for p in fac))\n",
    "        index = {p : i for i, p in enumerate(primes)}\n",
    "        parent = {i : i for i in range(len(primes))}\n",
    "        def find(node):\n",
    "            path = []\n",
    "            while node != parent[node]:\n",
    "                path.append(node)\n",
    "                node = parent[node]\n",
    "            for p in path:\n",
    "                parent[p] = node\n",
    "            return node\n",
    "        \n",
    "        def union(n1, n2):\n",
    "            p1 = find(n1)\n",
    "            p2 = find(n2)\n",
    "            if p1 != p2:\n",
    "                parent[p1] = p2 \n",
    "        counter = collections.Counter()\n",
    "        for fac in factors:\n",
    "            for p in fac[1:]:\n",
    "                union(index[p], index[fac[0]])\n",
    "        for fac in factors:\n",
    "            counter[find(index[fac[0]])] += 1 \n",
    "        return counter.most_common(1)[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        tree = dict(zip(nums, nums))\n",
    "\n",
    "        def parent(x):\n",
    "            cur = x\n",
    "            count = 0\n",
    "            while cur != tree[cur]:\n",
    "                cur = tree[cur]\n",
    "                count += 1\n",
    "            return cur, count\n",
    "\n",
    "        def merge(x, y):\n",
    "            px = parent(x)\n",
    "            py = parent(y)\n",
    "            if px[1] < py[1]:\n",
    "                tree[px[0]] = py[0]\n",
    "            else:\n",
    "                tree[py[0]] = px[0]\n",
    "        \n",
    "        fac_dic = {}\n",
    "        for k in nums:\n",
    "            p = 2\n",
    "            while p * p <= k:\n",
    "                if k % p == 0:\n",
    "                    if p in fac_dic:\n",
    "                        merge(fac_dic[p], k)\n",
    "                    if k // p in fac_dic:\n",
    "                        merge(fac_dic[k // p], k)\n",
    "                    fac_dic[p] = k\n",
    "                    fac_dic[k // p] = k\n",
    "                p += 1\n",
    "            if k in fac_dic:\n",
    "                merge(fac_dic[k], k)\n",
    "            fac_dic[k] = k\n",
    "        dic = defaultdict(int)\n",
    "        ans = 0\n",
    "        for k in nums:\n",
    "            pk = parent(k)[0]\n",
    "            dic[pk] += 1\n",
    "            ans = max(ans, dic[pk])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        factors = []\n",
    "        for num in nums:\n",
    "            fac = []\n",
    "            p = 2\n",
    "            while p * p <= num:\n",
    "                if num % p == 0:\n",
    "                    while num % p == 0:\n",
    "                        num //= p      \n",
    "                    fac.append(p)\n",
    "                p += 1 \n",
    "            if not fac or num > 1:\n",
    "                fac.append(num)\n",
    "            factors.append(fac)\n",
    "        primes = sorted(set(p for fac in factors for p in fac))\n",
    "        index = {p : i for i, p in enumerate(primes)}\n",
    "        parent = {i : i for i in range(len(primes))}\n",
    "        def find(node):\n",
    "            path = []\n",
    "            while node != parent[node]:\n",
    "                path.append(node)\n",
    "                node = parent[node]\n",
    "            for p in path:\n",
    "                parent[p] = node\n",
    "            return node\n",
    "        \n",
    "        def union(n1, n2):\n",
    "            p1 = find(n1)\n",
    "            p2 = find(n2)\n",
    "            if p1 != p2:\n",
    "                parent[p1] = p2 \n",
    "        counter = collections.Counter()\n",
    "        for fac in factors:\n",
    "            for p in fac[1:]:\n",
    "                union(index[p], index[fac[0]])\n",
    "        for fac in factors:\n",
    "            counter[find(index[fac[0]])] += 1 \n",
    "        return counter.most_common(1)[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class UnionFind:\n",
    "        def __init__(self, n):\n",
    "            self.parent = [i for i in range(n)]\n",
    "\n",
    "        def find(self, x):\n",
    "            if self.parent[x] != x:\n",
    "                self.parent[x] = self.find(self.parent[x])    \n",
    "            return self.parent[x]\n",
    "\n",
    "        def union(self, x, y):\n",
    "            rootx = self.find(x)\n",
    "            rooty = self.find(y)\n",
    "            if rootx != rooty:\n",
    "                self.parent[rootx] = rooty\n",
    "\n",
    "    def find_factors(self, num):\n",
    "        factors = []\n",
    "        for i in range(2, int(num ** 0.5) + 1):\n",
    "            if num % i == 0:\n",
    "                factors.append(i)\n",
    "                if i != num // i:\n",
    "                    factors.append(num // i)\n",
    "        return factors\n",
    "\n",
    "    def largestComponentSize(self, nums):\n",
    "        # 找到最大的数字\n",
    "        max_num = max(nums)\n",
    "\n",
    "        # 初始化并查集\n",
    "        uf = self.UnionFind(max_num + 1)\n",
    "\n",
    "        # 遍历数组中的每个数字\n",
    "        for num in nums:\n",
    "            # 找到数字的所有公因数\n",
    "            factors = self.find_factors(num)\n",
    "\n",
    "            # 将数字和公因数进行合并\n",
    "            for factor in factors:\n",
    "                uf.union(num, factor)\n",
    "\n",
    "        # 统计并查集中每个连通分量的大小\n",
    "        component_sizes = {}\n",
    "        largest_size = 0\n",
    "        for num in nums:\n",
    "            root = uf.find(num)\n",
    "            if root not in component_sizes:\n",
    "                component_sizes[root] = 0\n",
    "            component_sizes[root] += 1\n",
    "            largest_size = max(largest_size, component_sizes[root])\n",
    "\n",
    "        return largest_size\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        # 找到最小的公共因数\n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        def union(i, j):\n",
    "            p[find(i)] = find(j)\n",
    "        n = len(nums)\n",
    "        p = list(range(n))\n",
    "        primes = {}\n",
    "        for j, num in enumerate(nums):\n",
    "            fact = 2\n",
    "            while fact * fact <= num:\n",
    "                if not num % fact:\n",
    "                    if fact in primes:\n",
    "                        union(primes[fact], j)\n",
    "                    else:\n",
    "                        primes[fact] = j\n",
    "                    while not num % fact:\n",
    "                        num //= fact\n",
    "                fact += 1\n",
    "            if num > 1: # 有可能还剩下最大的一个素因数（最大素因数幂次为1才会出现在这里，一定要判断一下！）\n",
    "                if num in primes:\n",
    "                    union(primes[num], j)\n",
    "                else:\n",
    "                    primes[num] = j\n",
    "        cnt = [0] * n\n",
    "        for i in range(n):\n",
    "            cnt[find(i)] += 1\n",
    "        return max(cnt)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        n=max(nums)\n",
    "        Tree=[i for i in range(n+1)]\n",
    "\n",
    "        def find_root(idx):\n",
    "            while idx!=Tree[idx]:\n",
    "                Tree[idx]=Tree[Tree[idx]]\n",
    "                idx=Tree[idx]\n",
    "            return idx\n",
    "        \n",
    "        def gcd(a, b):\n",
    "            if b==0:\n",
    "                return a\n",
    "            return gcd(b,a%b)\n",
    "        \n",
    "        def merge(a, b):\n",
    "            roota=find_root(a)\n",
    "            rootb=find_root(b)\n",
    "            if roota==rootb:\n",
    "                return\n",
    "            Tree[roota]=rootb\n",
    "            return\n",
    "        for num in nums:\n",
    "            i=2\n",
    "            while i*i<=num:\n",
    "                if num%i==0:\n",
    "                    merge(num, i)\n",
    "                    merge(num, num//i)\n",
    "                i+=1\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i+1,n):\n",
    "        #         res=gcd(nums[i], nums[j])\n",
    "        #         if res>1:\n",
    "        #             roota=find_root(i)\n",
    "        #             rootb=find_root(j)\n",
    "        #             if roota!=rootb:\n",
    "        #                 Tree[roota]=rootb\n",
    "        mp=dict()\n",
    "        for num in nums:\n",
    "            root=find_root(num)\n",
    "            if root in mp:\n",
    "                mp[root]+=1\n",
    "            else:\n",
    "                mp[root]=1\n",
    "        max_ans=0\n",
    "        for key in mp.keys():\n",
    "            max_ans=max(max_ans,mp[key])\n",
    "        return max_ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        n=max(nums)\n",
    "        Tree=[i for i in range(n+1)]\n",
    "\n",
    "        def find_root(idx):\n",
    "            while idx!=Tree[idx]:\n",
    "                Tree[idx]=Tree[Tree[idx]]\n",
    "                idx=Tree[idx]\n",
    "            return idx\n",
    "        \n",
    "        def gcd(a, b):\n",
    "            if b==0:\n",
    "                return a\n",
    "            return gcd(b,a%b)\n",
    "        \n",
    "        def merge(a, b):\n",
    "            roota=find_root(a)\n",
    "            rootb=find_root(b)\n",
    "            if roota==rootb:\n",
    "                return\n",
    "            Tree[roota]=Tree[rootb]\n",
    "            return\n",
    "        for num in nums:\n",
    "            i=2\n",
    "            while i*i<=num:\n",
    "                if num%i==0:\n",
    "                    merge(num, i)\n",
    "                    merge(num, num//i)\n",
    "                i+=1\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i+1,n):\n",
    "        #         res=gcd(nums[i], nums[j])\n",
    "        #         if res>1:\n",
    "        #             roota=find_root(i)\n",
    "        #             rootb=find_root(j)\n",
    "        #             if roota!=rootb:\n",
    "        #                 Tree[roota]=rootb\n",
    "        mp=dict()\n",
    "        for num in nums:\n",
    "            root=find_root(num)\n",
    "            if root in mp:\n",
    "                mp[root]+=1\n",
    "            else:\n",
    "                mp[root]=1\n",
    "        max_ans=0\n",
    "        for key in mp.keys():\n",
    "            max_ans=max(max_ans,mp[key])\n",
    "        return max_ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n):\n",
    "        self.states = [i for i in range(n)]\n",
    "    \n",
    "    def find(self, i):\n",
    "        if self.states[i] != i: self.states[i] = self.find(self.states[i])\n",
    "        return self.states[i]\n",
    "    \n",
    "    def union(self, i, j):\n",
    "        self.states[self.find(i)] = self.find(j)\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        n = max(nums)\n",
    "        res, dsu = [], DSU(n + 1)\n",
    "        for num in nums:\n",
    "            tmp, base, val = num, -1, 2\n",
    "            while val * val <= num and val <= tmp:\n",
    "                if tmp % val == 0:\n",
    "                    if base == -1: base = val\n",
    "                    else: dsu.union(val, base)\n",
    "                    tmp //= val\n",
    "                else: val += 1\n",
    "            if tmp > 1:\n",
    "                if base == -1: base = tmp\n",
    "                else: dsu.union(tmp, base)\n",
    "            res.append(base)\n",
    "        cnts = collections.defaultdict(int)\n",
    "        for d in res: cnts[dsu.find(d)] += 1\n",
    "        ans = 1\n",
    "        for k in cnts: ans = max(ans, cnts[k])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        class UF:\n",
    "            def __init__(self,n):\n",
    "                self.parents = list(range(n))\n",
    "                \n",
    "            def find(self,x):\n",
    "                if self.parents[x] != x:\n",
    "                    self.parents[x] = self.find(self.parents[x])\n",
    "                return(self.parents[x])\n",
    "            \n",
    "            def union(self,x,y):\n",
    "                root_x = self.find(x)\n",
    "                root_y = self.find(y)\n",
    "                self.parents[root_x] = root_y\n",
    "                \n",
    "            \n",
    "        n = max(nums)+1\n",
    "        uf = UF(n)\n",
    "\n",
    "        for num in nums:\n",
    "            i = 2\n",
    "            while num/i >= i:\n",
    "                if num % i == 0:\n",
    "                    uf.union(num,i)\n",
    "                    uf.union(num,num//i)\n",
    "                i += 1\n",
    "                \n",
    "        root_final = [uf.find(x) for x in nums ]\n",
    "        return(max(Counter(root_final).values()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [0] * n\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def merge(self, x: int, y: int) -> None:\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x == y:\n",
    "            return\n",
    "        if self.rank[x] > self.rank[y]:\n",
    "            self.parent[y] = x\n",
    "        elif self.rank[x] < self.rank[y]:\n",
    "            self.parent[x] = y\n",
    "        else:\n",
    "            self.parent[y] = x\n",
    "            self.rank[x] += 1\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        uf = UnionFind(max(nums) + 1)\n",
    "        for num in nums:\n",
    "            i = 2\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    uf.merge(num, i)\n",
    "                    uf.merge(num, num // i)\n",
    "                i += 1\n",
    "        return max(Counter(uf.find(num) for num in nums).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [0] * n\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def merge(self, x: int, y: int) -> None:\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x == y:\n",
    "            return\n",
    "        if self.rank[x] > self.rank[y]:\n",
    "            self.parent[y] = x\n",
    "        elif self.rank[x] < self.rank[y]:\n",
    "            self.parent[x] = y\n",
    "        else:\n",
    "            self.parent[y] = x\n",
    "            self.rank[x] += 1\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        uf = UnionFind(max(nums) + 1)\n",
    "        for num in nums:\n",
    "            i = 2\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    uf.merge(num, i)\n",
    "                    uf.merge(num, num // i)\n",
    "                i += 1\n",
    "        return max(Counter(uf.find(num) for num in nums).values())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [0] * n\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def merge(self, x: int, y: int) -> None:\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x == y:\n",
    "            return\n",
    "        if self.rank[x] > self.rank[y]:\n",
    "            self.parent[y] = x\n",
    "        elif self.rank[x] < self.rank[y]:\n",
    "            self.parent[x] = y\n",
    "        else:\n",
    "            self.parent[y] = x\n",
    "            self.rank[x] += 1\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        uf = UnionFind(max(nums) + 1)\n",
    "        for num in nums:\n",
    "            i = 2\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    uf.merge(num, i)\n",
    "                    uf.merge(num, num // i)\n",
    "                i += 1\n",
    "        return max(Counter(uf.find(num) for num in nums).values())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [0] * n\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def merge(self, x: int, y: int) -> None:\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x == y:\n",
    "            return\n",
    "        if self.rank[x] > self.rank[y]:\n",
    "            self.parent[y] = x\n",
    "        elif self.rank[x] < self.rank[y]:\n",
    "            self.parent[x] = y\n",
    "        else:\n",
    "            self.parent[y] = x\n",
    "            self.rank[x] += 1\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        uf = UnionFind(max(nums) + 1)\n",
    "        for num in nums:\n",
    "            i = 2\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    uf.merge(num, i)\n",
    "                    uf.merge(num, num // i)\n",
    "                i += 1\n",
    "        return max(Counter(uf.find(num) for num in nums).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        # 统计一个正整数的质因数（素因子）\n",
    "        def getPrimeFactors(num):\n",
    "            factors = set()\n",
    "            i = 2\n",
    "            while i * i <= num:  # num = 18\n",
    "                if num % i == 0:\n",
    "                    factors.add(i)\n",
    "                    num //= i\n",
    "                else:\n",
    "                    i += 1\n",
    "            if num > 1:\n",
    "                factors.add(num)\n",
    "            return factors\n",
    "\n",
    "        n = len(nums)\n",
    "        parent = list(range(n))\n",
    "        sizes = [1] * n\n",
    "\n",
    "        def find(x):\n",
    "            if x != parent[x]:\n",
    "                parent[x] = find(parent[x])\n",
    "\n",
    "            return parent[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            root_x, root_y = find(x), find(y)\n",
    "            if root_x < root_y:\n",
    "                parent[root_y] = root_x\n",
    "                sizes[root_x] += sizes[root_y]\n",
    "            elif root_x > root_y:\n",
    "                parent[root_x] = root_y\n",
    "                sizes[root_y] += sizes[root_x]\n",
    "            else:\n",
    "                pass\n",
    "\n",
    "        factor_dict = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            factors = getPrimeFactors(num)\n",
    "            if not factors:  # num是质数\n",
    "                factor_dict[num] = i\n",
    "\n",
    "            for factor in factors:  # num是合数\n",
    "                if factor not in factor_dict:\n",
    "                    factor_dict[factor] = i\n",
    "                else:\n",
    "                    union(i, factor_dict[factor])\n",
    "        return max(sizes)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [0] * n\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def merge(self, x: int, y: int) -> None:\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x == y:\n",
    "            return\n",
    "        if self.rank[x] > self.rank[y]:\n",
    "            self.parent[y] = x\n",
    "        elif self.rank[x] < self.rank[y]:\n",
    "            self.parent[x] = y\n",
    "        else:\n",
    "            self.parent[y] = x\n",
    "            self.rank[x] += 1\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        uf = UnionFind(max(nums) + 1)\n",
    "        for num in nums:\n",
    "            i = 2\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    uf.merge(num, i)\n",
    "                    uf.merge(num, num // i)\n",
    "                i += 1\n",
    "        return max(Counter(uf.find(num) for num in nums).values())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [0] * n\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def merge(self, x: int, y: int) -> None:\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x == y:\n",
    "            return\n",
    "        if self.rank[x] > self.rank[y]:\n",
    "            self.parent[y] = x\n",
    "        elif self.rank[x] < self.rank[y]:\n",
    "            self.parent[x] = y\n",
    "        else:\n",
    "            self.parent[y] = x\n",
    "            self.rank[x] += 1\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        uf = UnionFind(max(nums) + 1)\n",
    "        for num in nums:\n",
    "            i = 2\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    uf.merge(num, i)\n",
    "                    uf.merge(num, num // i)\n",
    "                i += 1\n",
    "        return max(Counter(uf.find(num) for num in nums).values())\n",
    "\n",
    "A = Solution()\n",
    "print(A.largestComponentSize([4, 6, 15, 35]))\n",
    "print(A.largestComponentSize([20, 50, 9, 63]))\n",
    "print(A.largestComponentSize([2, 3, 6, 7, 4, 12, 21, 39]))\n",
    "\n",
    "# leetcode submit region end(Prohibit modification and deletion)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Union:\n",
    "    #### 注意！！！python的类中都应该有self！！！\n",
    "    ##### 参数变量可以没有self！！！但全局函数及全局变量应该有self！！！\n",
    "    def __init__(self, num: int) -> None:\n",
    "        # 注意用python怎样进行初始化！！！\n",
    "        self.parents = list(range(num))\n",
    "        self.rank = [0] * num\n",
    "    \n",
    "    def find(self, x: int) -> int:\n",
    "        ### 注意什么时候改用self， 什么时候不该用self!!!\n",
    "        if x != self.parents[x]:\n",
    "            self.parents[x] = self.find(self.parents[x])\n",
    "        return self.parents[x]\n",
    "\n",
    "    def merge(self, x: int, y: int) -> None:\n",
    "        px = self.find(x)\n",
    "        py = self.find(y)\n",
    "        if px == py:\n",
    "            return \n",
    "        if self.rank[px] < self.rank[py]:\n",
    "            self.parents[px] = self.parents[py]\n",
    "        elif self.rank[px] > self.rank[py]:\n",
    "            self.parents[py] = self.parents[px]\n",
    "        else:\n",
    "            self.parents[py] = self.parents[px]\n",
    "            self.rank[px] += 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        un = Union(max(nums) + 1)\n",
    "        for num in nums:\n",
    "            i = 2\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    un.merge(num, i)\n",
    "                    un.merge(num, num // i)\n",
    "                ### 注意别忘了i要逐步增加！！！别把i给忘了！！！\n",
    "                i += 1\n",
    "        ### 注意python中counter的灵活使用！！！\n",
    "        ans = max(Counter(un.find(num) for num in nums).values())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        n = max(nums)+1\n",
    "        parent = [x for x in range(n)]\n",
    "        tree_num = [1] * n\n",
    "        def find(node):\n",
    "            while parent[node] != node:\n",
    "                parent[node] = parent[parent[node]]\n",
    "                node = parent[node]\n",
    "            return node\n",
    "        def merge(x, y):\n",
    "            root_x, root_y = find(x), find(y)\n",
    "            if root_x == root_y:\n",
    "                return \n",
    "            if tree_num[root_x]>tree_num[root_y]:\n",
    "                parent[root_y] = root_x\n",
    "                tree_num[root_x] += tree_num[root_y]\n",
    "            else:\n",
    "                parent[root_x] = root_y\n",
    "                tree_num[root_y] += tree_num[root_x]\n",
    "        for num in nums:\n",
    "            i = 2\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    merge(num, i)\n",
    "                    merge(num, num//i)\n",
    "                i+=1\n",
    "        return max((Counter([find(num) for num in nums])).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = [x for x in range(n)]\n",
    "        self.size = [1 for _ in range(n)]\n",
    "        self.part = n\n",
    "    \n",
    "    def Find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.Find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def Union(self, x: int, y: int) -> bool:\n",
    "        root_x = self.Find(x)\n",
    "        root_y = self.Find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] > self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.parent[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def get_part_size(self, x: int) -> int:\n",
    "        root_x = self.Find(x)\n",
    "        return self.size[root_x]\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        n = max(nums)\n",
    "        UF = UnionFind(n + 1)\n",
    "        for num in nums:\n",
    "            for x in range(2, int(num ** 0.5) + 1):\n",
    "                if num % x == 0:\n",
    "                    UF.Union(num, num // x)\n",
    "                    UF.Union(num, x)\n",
    "        dic = defaultdict(int)\n",
    "        for num in nums:\n",
    "            dic[UF.Find(num)] += 1\n",
    "        return max(dic.values())        #连接结点最多的那个因子， 的连接频率\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [0] * n\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def merge(self, x: int, y: int) -> None:\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x == y:\n",
    "            return\n",
    "        if self.rank[x] > self.rank[y]:\n",
    "            self.parent[y] = x\n",
    "        elif self.rank[x] < self.rank[y]:\n",
    "            self.parent[x] = y\n",
    "        else:\n",
    "            self.parent[y] = x\n",
    "            self.rank[x] += 1\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        uf = UnionFind(max(nums) + 1)\n",
    "        for num in nums:\n",
    "            i = 2\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    uf.merge(num, i)\n",
    "                    uf.merge(num, num // i)\n",
    "                i += 1\n",
    "        return max(Counter(uf.find(num) for num in nums).values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        # 统计一个正整数的质因数（素因子）\n",
    "        def getPrimeFactors(num):\n",
    "            factors = set()\n",
    "            i = 2\n",
    "            while i * i <= num:  # num = 18\n",
    "                if num % i == 0:\n",
    "                    factors.add(i)\n",
    "                    num //= i\n",
    "                else:\n",
    "                    i += 1\n",
    "            if num > 1:\n",
    "                factors.add(num)\n",
    "            return factors\n",
    "\n",
    "        n = len(nums)\n",
    "        parent = list(range(n))\n",
    "        sizes = [1] * n\n",
    "\n",
    "        def find(x):\n",
    "            if x != parent[x]:\n",
    "                parent[x] = find(parent[x])\n",
    "\n",
    "            return parent[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            root_x, root_y = find(x), find(y)\n",
    "            if root_x < root_y:\n",
    "                parent[root_y] = root_x\n",
    "                sizes[root_x] += sizes[root_y]\n",
    "            elif root_x > root_y:\n",
    "                parent[root_x] = root_y\n",
    "                sizes[root_y] += sizes[root_x]\n",
    "            else:\n",
    "                pass\n",
    "\n",
    "        factor_dict = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            factors = getPrimeFactors(num)\n",
    "\n",
    "            for factor in factors:  \n",
    "                if factor not in factor_dict:\n",
    "                    factor_dict[factor] = i\n",
    "                else:\n",
    "                    union(i, factor_dict[factor])\n",
    "        return max(sizes)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    \"\"\"\n",
    "    并查集\n",
    "    \"\"\"\n",
    "    def __init__(self, size):\n",
    "        self.max_size = 1    \n",
    "        self.father = [-1 for _ in range(size)] #记录下各个节点的父节点, 属于哪一个集合\n",
    "        self.set_size = [1 for _ in range(size)]    #记录下各个集合的大小\n",
    "\n",
    "    def findFather(self, node):\n",
    "        \"\"\"\n",
    "        寻找节点node的父亲节点\n",
    "        \"\"\"\n",
    "        neighbor_nodes = [] #用于记录下沿途的同父的节点, 为了方便用于处理\n",
    "        while self.father[node] != -1:\n",
    "            neighbor_nodes.append(node)\n",
    "            node = self.father[node]\n",
    "        \n",
    "        #压缩路径\n",
    "        for ne_node in neighbor_nodes:\n",
    "            self.father[ne_node] = node \n",
    "\n",
    "        return node \n",
    "    \n",
    "\n",
    "    def union(self, node1, node2):\n",
    "        \"\"\"\n",
    "        将两个节点联合成同一集合\n",
    "\n",
    "        \"\"\"\n",
    "        #求解两个节点的父亲节点, 属于哪一个集合\n",
    "        father1, father2 = self.findFather(node1), self.findFather(node2)\n",
    "\n",
    "        if father1 != father2:\n",
    "            #将小集合合并到大集合之上\n",
    "            father_size1 = self.set_size[father1]\n",
    "            father_size2 = self.set_size[father2]\n",
    "\n",
    "            if father1 < father2:\n",
    "                self.father[father1] = father2\n",
    "                self.set_size[father2] += self.set_size[father1]\n",
    "                if self.set_size[father2] > self.max_size:\n",
    "                    self.max_size = self.set_size[father2]\n",
    "\n",
    "            else:\n",
    "                self.father[father2] = father1\n",
    "                self.set_size[father1] += self.set_size[father2]\n",
    "                if self.set_size[father1] > self.max_size:\n",
    "                    self.max_size = self.set_size[father1]\n",
    "\n",
    "import math \n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums):\n",
    "        \"\"\"\n",
    "        对于含有同一因子的数属于同一类, 求解数组中同一类的最大数量\n",
    "        Args:\n",
    "            nums (list[int]): 目标数组\n",
    "        returns (int): 同一集合之中的最大数量\n",
    "        \"\"\"\n",
    "        #处理异常情况\n",
    "        if nums == None:\n",
    "            return 0 \n",
    "        n = len(nums)\n",
    "\n",
    "        if n < 2:\n",
    "            return n \n",
    "        \n",
    "        #使用字典记录下各个因子的索引号, key: 因子, value: index, 该因子位于数组之中的索引\n",
    "        map_dict = {}\n",
    "\n",
    "        #创建并查集, 将含有同一因子的合并为一个集合\n",
    "        union_find = UnionFind(n)\n",
    "\n",
    "        #遍历数组\n",
    "        for i, num in enumerate(nums):\n",
    "            #因子分解 1 ~ num**0.5 \n",
    "            limit = int(math.sqrt(num))\n",
    "\n",
    "            #若字典中含有该因子, 将其合并\n",
    "            for j in range(1, limit + 1):\n",
    "                if num % j == 0:\n",
    "                    if j != 1 and not map_dict.__contains__(j):\n",
    "                        map_dict[j] = i  \n",
    "\n",
    "                    elif j != 1 and map_dict.__contains__(j):\n",
    "                        union_find.union(i, map_dict[j])\n",
    "                \n",
    "                    other = num // j \n",
    "\n",
    "                    if not map_dict.__contains__(other):\n",
    "                        map_dict[other] = i  \n",
    "\n",
    "                    else:\n",
    "                        union_find.union(i, map_dict[other])\n",
    "\n",
    "        return union_find.max_size\n",
    "\n",
    "    def gcd(self, a, b):\n",
    "        \"\"\"\n",
    "        辗转相除求解两数的最大公约数\n",
    "        Args:\n",
    "            a (int): 目标数1\n",
    "            b (int): 目标数2\n",
    "        returns (int): 最大公约数\n",
    "        \"\"\"\n",
    "        if b == 0:\n",
    "            return a \n",
    "        \n",
    "        return self.gcd(b, a % b)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,n):\n",
    "        self.father = [i for i in range(n + 1)]\n",
    "        self.rank = [1] * (n + 1)\n",
    "\n",
    "    def find(self,x):\n",
    "        if self.father[x]!=x:\n",
    "            self.father[x] = self.find(self.father[x])\n",
    "        return self.father[x]\n",
    "    \n",
    "    def union(self,x,y):\n",
    "        x_father,y_father = self.find(x),self.find(y)\n",
    "        \n",
    "        if x_father == y_father:\n",
    "            return\n",
    "        \n",
    "        # if self.rank[x_father]>self.rank[y_father]:\n",
    "        #     self.father[y_father] = x_father\n",
    "        # elif self.rank[x_father]<self.rank[y_father]:\n",
    "        #     self.father[x_father] = y_father\n",
    "        # else:\n",
    "        #     self.father[y_father] = x_father\n",
    "        #     self.rank[x_father]+=1\n",
    "        if self.rank[x_father]<self.rank[y_father]:\n",
    "            x_father,y_father = y_father,x_father\n",
    "        self.rank[x_father]+=self.rank[y_father]\n",
    "        self.father[y_father] = x_father\n",
    "\n",
    "    def is_connected(self,x,y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        uf = UnionFind(max(nums))\n",
    "        for num in nums:\n",
    "            i = 2\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    uf.union(num,i)\n",
    "                    uf.union(num,num//i)\n",
    "                i += 1\n",
    "        return max(Counter(uf.find(num) for num in nums).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [0] * n\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def merge(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x == y:\n",
    "            return None\n",
    "        if self.rank[x] > self.rank[y]:\n",
    "            self.parent[y] = x\n",
    "        elif self.rank[x] < self.rank[y]:\n",
    "            self.parent[x] = y\n",
    "        else:\n",
    "            self.parent[y] = x\n",
    "            self.rank[x] += 1\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        uf = UF(max(nums)+1)\n",
    "        for num in nums:\n",
    "            i = 2\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    uf.merge(num, i)\n",
    "                    uf.merge(num, num // i)\n",
    "                i += 1\n",
    "        return max(Counter([uf.find(num) for num in nums]).values())\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10**5\n",
    "minp = [0] * (MX + 1)\n",
    "primes = []\n",
    "for x in range(2, MX + 1):\n",
    "    if minp[x] == 0:\n",
    "        minp[x] = x\n",
    "        primes.append(x)\n",
    "    for p in primes:\n",
    "        if x * p > MX:\n",
    "            break\n",
    "        minp[x * p] = p\n",
    "        if p == minp[x]:\n",
    "            break\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pa = list(range(n))\n",
    "        size = [1] * n\n",
    "\n",
    "        def find(x):\n",
    "            if pa[x] != x:\n",
    "                pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "        \n",
    "        def union(x, y):\n",
    "            rx, ry = find(x), find(y)\n",
    "            if rx != ry:\n",
    "                if size[rx] < size[ry]:\n",
    "                    rx, ry = ry, rx\n",
    "                pa[ry] = rx\n",
    "                size[rx] += size[ry]\n",
    "\n",
    "        factors = {}\n",
    "        for i, x in enumerate(nums):\n",
    "            while x > 1:\n",
    "                p = minp[x]\n",
    "                if p in factors:\n",
    "                    union(i, factors[p])\n",
    "                else:\n",
    "                    factors[p] = i\n",
    "                while x % p == 0:\n",
    "                    x //= p\n",
    "\n",
    "        return max(size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        # 统计一个正整数的质因数（素因子）\n",
    "        def getPrimeFactors(num):\n",
    "            factors = set()\n",
    "            i = 2\n",
    "            while i * i <= num:  # num = 18\n",
    "                if num % i == 0:\n",
    "                    factors.add(i)\n",
    "                    num //= i\n",
    "                else:\n",
    "                    i += 1\n",
    "            if num > 1:\n",
    "                factors.add(num)\n",
    "            return factors\n",
    "\n",
    "        n = len(nums)\n",
    "        parent = list(range(n))\n",
    "        sizes = [1] * n\n",
    "        self.max_size = 1\n",
    "\n",
    "        def find(x):\n",
    "            if x != parent[x]:\n",
    "                parent[x] = find(parent[x])\n",
    "\n",
    "            return parent[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            root_x, root_y = find(x), find(y)\n",
    "            if root_x != root_y:\n",
    "                parent[root_x] = root_y\n",
    "                sizes[root_y] += sizes[root_x]\n",
    "                # nonlocal max_size\n",
    "                self.max_size = max(self.max_size, sizes[root_y])\n",
    "\n",
    "        factor_dict = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            factors = getPrimeFactors(num)\n",
    "\n",
    "            for factor in factors:  \n",
    "                if factor not in factor_dict:\n",
    "                    factor_dict[factor] = i\n",
    "                else:\n",
    "                    union(factor_dict[factor], i)\n",
    "\n",
    "        return self.max_size\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        # 统计一个正整数的质因数（素因子）\n",
    "        def getPrimeFactors(num):\n",
    "            factors = set()\n",
    "            i = 2\n",
    "            while i * i <= num:  # num = 18\n",
    "                if num % i == 0:\n",
    "                    factors.add(i)\n",
    "                    num //= i\n",
    "                else:\n",
    "                    i += 1\n",
    "            if num > 1:\n",
    "                factors.add(num)\n",
    "            return factors\n",
    "\n",
    "        n = len(nums)\n",
    "        parent = list(range(n))\n",
    "        sizes = [1] * n\n",
    "        # self.max_size = 1\n",
    "\n",
    "        def find(x):\n",
    "            if x != parent[x]:\n",
    "                parent[x] = find(parent[x])\n",
    "\n",
    "            return parent[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            root_x, root_y = find(x), find(y)\n",
    "            if root_x != root_y:\n",
    "                parent[root_x] = root_y\n",
    "                sizes[root_y] += sizes[root_x]\n",
    "                # nonlocal max_size\n",
    "                # self.max_size = max(self.max_size, sizes[root_y])\n",
    "\n",
    "        factor_dict = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            factors = getPrimeFactors(num)\n",
    "\n",
    "            for factor in factors:  \n",
    "                if factor not in factor_dict:\n",
    "                    factor_dict[factor] = i\n",
    "                else:\n",
    "                    union(factor_dict[factor], i)\n",
    "\n",
    "        return max(sizes)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# ref:https://leetcode.cn/problems/largest-component-size-by-common-factor/solutions/1268384/mei-tian-yi-dao-kun-nan-ti-di-31tian-zui-4axh/\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        max_num = max(nums)\n",
    "        n = len(nums)\n",
    "        parents = [i for i in range(n)]\n",
    "        size = [1] * n\n",
    "        def find(x):\n",
    "            if x == parents[x]:\n",
    "                return x\n",
    "            parents[x] = find(parents[x])\n",
    "            return parents[x]\n",
    "        def union(x,y):\n",
    "            parent_x,parent_y = find(x),find(y)\n",
    "            if parent_x == parent_y:\n",
    "                return\n",
    "            if size[parent_x] > size[parent_y]:\n",
    "                parents[parent_y] = parent_x\n",
    "                size[parent_x] += size[parent_y]\n",
    "            else:\n",
    "                parents[parent_x] = parent_y\n",
    "                size[parent_y] += size[parent_x]\n",
    "\n",
    "        def factor(a):\n",
    "            ans = set()\n",
    "            for i in range(1,int(math.sqrt(a))+1):\n",
    "                if a%i == 0:\n",
    "                    f1, f2 = i, a//i\n",
    "                    if f1 != 1:\n",
    "                        ans.add(f1)\n",
    "                    if f2 != 1:\n",
    "                        ans.add(f2)\n",
    "            return ans\n",
    "\n",
    "        lookup = defaultdict(list)\n",
    "        for i,v in enumerate(nums):\n",
    "            factors = factor(v)\n",
    "            for f in factors:\n",
    "                lookup[f].append(i)\n",
    "\n",
    "        for f in lookup.keys():\n",
    "\n",
    "            to_union = lookup[f]\n",
    "            length = len(to_union)\n",
    "            for i in range(1,length):\n",
    "                union(to_union[i],to_union[i-1])\n",
    "\n",
    "        return max(size)\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(x):\n",
    "    ans = []\n",
    "    for j in range(2, x+1):\n",
    "        if j*j>x:\n",
    "            break \n",
    "        else:\n",
    "            while (x%j)==0:\n",
    "                x = x//j\n",
    "                ans.append(j)\n",
    "    if x>1:\n",
    "        ans.append(x)\n",
    "    return set(ans)\n",
    "        \n",
    "    \n",
    "    \n",
    "class Solution:\n",
    "    def largestComponentSize(self, a: List[int]) -> int:\n",
    "        self.ans = 1\n",
    "        g = defaultdict(set)\n",
    "        for j in range(len(a)):\n",
    "            tmp = f(a[j])\n",
    "            if tmp:\n",
    "                for k in tmp:\n",
    "                    g[str(k)].add(j)\n",
    "                    g[j].add(str(k))\n",
    "        v = set()\n",
    "        def bfs(x):\n",
    "            if x in v:\n",
    "                return \n",
    "            v.add(x)\n",
    "            s = [x]\n",
    "            ans = [x]\n",
    "            while s:\n",
    "                tmp = []\n",
    "                for j in s:\n",
    "                    for k in g[j]:\n",
    "                        if k not in v:\n",
    "                            v.add(k)\n",
    "                            tmp.append(k)\n",
    "                s = tmp\n",
    "                ans += s\n",
    "            ans = [j for j in ans if type(j)==int]\n",
    "            self.ans = max(self.ans, len(ans))\n",
    "        for j in g:\n",
    "            bfs(j)\n",
    "        return self.ans\n",
    "        \n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "                    n = len(nums)\n",
    "                    nums.sort()\n",
    "                    index = Counter()\n",
    "                    p = [i for i in range(n+1)]\n",
    "                    cnt = [1] * (n+1);cnt[0] = 0\n",
    "                    def find(x):\n",
    "                        if p[x] != x:p[x] = find(p[x])\n",
    "                        return p[x]\n",
    "                    def merge(x,y):\n",
    "                        x = find(x)\n",
    "                        y = find(y)\n",
    "                        if x != y:\n",
    "                            p[x] = y\n",
    "                            cnt[y] += cnt[x]\n",
    "                    for i,x in enumerate(nums,1):\n",
    "                        index[x] = i\n",
    "                    \n",
    "                    g = defaultdict(set)\n",
    "                    t = int(sqrt(nums[-1])) + 1\n",
    "                    for i in nums:\n",
    "                        for j in range(2,t):\n",
    "                            if i%j == 0:\n",
    "                                g[j].add(i)\n",
    "                                if index[i//j]>0 and i//j!=1:\n",
    "                                    g[j].add(i//j)\n",
    "                                if i//j>1:g[i//j].add(i)\n",
    "                    # print(g)\n",
    "                    for k in g.keys():\n",
    "                        d = -1\n",
    "                        for u in g[k]:\n",
    "                            \n",
    "                            if d == -1:d = index[u]\n",
    "                            else:merge(index[u],d)\n",
    "                    return max(cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 100000\n",
    "prime = [[] for _ in range(N+1)]\n",
    "for i in range(2, N+1):\n",
    "    p, x = 2, i\n",
    "    while p*p <= x:\n",
    "        if x % p == 0:\n",
    "            prime[i].append(p)\n",
    "            while x % p == 0:\n",
    "                x //= p\n",
    "        p += 1\n",
    "    if x > 1:\n",
    "        prime[i].append(x)\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        # 并查集\n",
    "        fa, size = list(range(n)), [1]*n\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(x: int, y: int) -> int:\n",
    "            x, y = find(x), find(y)\n",
    "            if x == y: \n",
    "                return y\n",
    "            fa[x] = y\n",
    "            size[y] += size[x]\n",
    "            return y\n",
    "        # 该字典记录每个质因子对应的num\n",
    "        dic = defaultdict(list)\n",
    "        for i, num in enumerate(nums):\n",
    "            for p in prime[num]:\n",
    "                dic[p].append(i)\n",
    "        # 合并同一质因子的num\n",
    "        for v in dic.values():\n",
    "            reduce(merge, v)\n",
    "        # print(fa)\n",
    "        # print(size)\n",
    "        return max(size)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10**5\n",
    "prime = [[] for _ in range(N+1)]\n",
    "for i in range(2, N+1):\n",
    "    p, x = 2, i\n",
    "    while p*p <= x:\n",
    "        if x % p == 0:\n",
    "            prime[i].append(p)\n",
    "            while x % p == 0:\n",
    "                x //= p\n",
    "        p += 1\n",
    "    if x > 1:\n",
    "        prime[i].append(x)\n",
    "# print(prime)\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        # 并查集\n",
    "        fa, size = list(range(n)), [1]*n\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(x: int, y: int) -> int:\n",
    "            x, y = find(x), find(y)\n",
    "            if x == y: \n",
    "                return y\n",
    "            fa[x] = y\n",
    "            size[y] += size[x]\n",
    "            return y\n",
    "        # 该字典记录每个质因子对应的num\n",
    "        dic = defaultdict(list)\n",
    "        for i, num in enumerate(nums):\n",
    "            for p in prime[num]:\n",
    "                dic[p].append(i)\n",
    "        # 合并同一质因子的num\n",
    "        for v in dic.values():\n",
    "            reduce(merge, v)\n",
    "        # print(fa)\n",
    "        # print(size)\n",
    "        return max(size)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        \n",
    "        def dfs(i):\n",
    "            vis[i] = True\n",
    "            if i in ss:\n",
    "                ans = 1\n",
    "            else:\n",
    "                ans = 0\n",
    "            for j in g[i]:\n",
    "                if not vis[j]:\n",
    "                    ans += dfs(j)\n",
    "            return ans\n",
    "        \n",
    "        from collections import defaultdict\n",
    "        g = defaultdict(list)\n",
    "        vis = defaultdict(bool)\n",
    "\n",
    "        ss = set(nums)\n",
    "        ans = 1\n",
    "        for num in nums:\n",
    "            i = 2\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    g[num].append(i)\n",
    "                    g[i].append(num)\n",
    "                    g[num // i].append(num)\n",
    "                    g[num].append(num // i)\n",
    "                i += 1\n",
    "\n",
    "        for i in g:\n",
    "            if not vis[i]:\n",
    "                ans = max(ans, dfs(i))\n",
    "        # print(g)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        g = defaultdict(list) \n",
    "        table = [0] * 100001 \n",
    "        for i in range(n):\n",
    "            table[nums[i]] = 1\n",
    "        for d in range(2, 100001):\n",
    "            for j in range(d, 100001, d):\n",
    "                if table[j]:\n",
    "                    g[j].append(d+100001)\n",
    "                    g[d+100001].append(j)\n",
    "\n",
    "        vis = [0] * 200011\n",
    "        cnt = 0\n",
    "        def dfs(x):\n",
    "            nonlocal cnt \n",
    "            vis[x] = 1\n",
    "            if x < 100001:\n",
    "                cnt += 1\n",
    "            for y in g[x]:\n",
    "                if not vis[y]:\n",
    "                    dfs(y)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if not vis[nums[i]]:\n",
    "                dfs(nums[i])\n",
    "                ans = max(ans, cnt)\n",
    "                cnt = 0\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\r\n",
    "        n = max(nums) + 1\r\n",
    "        pa = list(range(n))\r\n",
    "        sz = [0] * n\r\n",
    "        vis = [False] * n\r\n",
    "\r\n",
    "        def find(i: int) -> int:\r\n",
    "            if pa[i] != i: pa[i] = find(pa[i])\r\n",
    "            return pa[i]\r\n",
    "        \r\n",
    "        def join(i: int, j: int) -> None:\r\n",
    "            f, g = find(i), find(j)\r\n",
    "            if f == g: return\r\n",
    "            if sz[f] > sz[g]:\r\n",
    "                sz[f] += sz[g]\r\n",
    "                pa[g] = f\r\n",
    "            else:\r\n",
    "                sz[g] += sz[f]\r\n",
    "                pa[f] = g\r\n",
    "        \r\n",
    "        for num in nums: sz[num] += 1\r\n",
    "        for i in range(2, n):\r\n",
    "            if vis[i]: continue\r\n",
    "            j = 2 * i\r\n",
    "            while j < n:\r\n",
    "                if sz[j] > 0:\r\n",
    "                    join(i, j)\r\n",
    "                vis[j] = True\r\n",
    "                j += i\r\n",
    "        \r\n",
    "        return max(sz)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        m = max(nums)+1\n",
    "        parent = list(range(m))\n",
    "        rank = [0] * m\n",
    "        def find(i) -> int:\n",
    "            if parent[i] != i:\n",
    "                parent[i] = find(parent[i])\n",
    "            return parent[i]\n",
    "        \n",
    "        def union(i, j):\n",
    "            pi = find(i)\n",
    "            pj = find(j)\n",
    "            if pi != pj:\n",
    "                if rank[pi] < rank[pj]:\n",
    "                    parent[pi] = parent[pj]\n",
    "                else:\n",
    "                    parent[pj] = parent[pi]\n",
    "                    if rank[pi] == rank[pj]:\n",
    "                        rank[pi] += 1\n",
    "\n",
    "        for num in nums:\n",
    "            n = 2\n",
    "            while n*n <= num:\n",
    "                if num%n == 0:\n",
    "                    union(num, n)\n",
    "                    union(num, num//n)\n",
    "                n += 1\n",
    "        \n",
    "        return max(Counter(find(i) for i in nums).values())\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        root_list = list(range(max(nums) + 1))\n",
    "        rank_list = [0] * (max(nums) + 1)\n",
    "\n",
    "        def find_root(v):\n",
    "            if root_list[v] != v:\n",
    "                root_list[v] = find_root(root_list[v])\n",
    "            return root_list[v]\n",
    "\n",
    "        def add(v, v_up):\n",
    "            v_root = find_root(v)\n",
    "            v_up_root = find_root(v_up)\n",
    "            if v_root == v_up_root:\n",
    "                return\n",
    "            if rank_list[v_root] > rank_list[v_up_root]:\n",
    "                root_list[v_up_root] = v_root\n",
    "            elif rank_list[v_root] < rank_list[v_up_root]:\n",
    "                root_list[v_root] = v_up_root\n",
    "            else:\n",
    "                root_list[v_up_root] = v_root\n",
    "                rank_list[v_root] += 1\n",
    "\n",
    "        for num in nums:\n",
    "            i = 2\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    add(num, i)\n",
    "                    add(num, num // i)\n",
    "                i += 1\n",
    "        return max(Counter(find_root(num) for num in nums ).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        def find(x):\n",
    "            if x != p[x]:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        \n",
    "        n = len(nums)\n",
    "        p = [i for i in range(max(nums)+1)]\n",
    "        for num in nums:\n",
    "            i = 2\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    p[find(num)] = find(i)\n",
    "                    p[find(num)] = find(num // i)\n",
    "                i += 1\n",
    "        \n",
    "        return max(Counter(find(x) for x in nums).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        maxnum=max(nums)+1\n",
    "        n=len(nums)\n",
    "        fa=[0]*maxnum\n",
    "        for i in range(maxnum):\n",
    "            fa[i]=i\n",
    "        def find(x):\n",
    "            nonlocal fa\n",
    "            if x==fa[x]:\n",
    "                return x\n",
    "            fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        def unionf(x,y):\n",
    "            nonlocal fa\n",
    "            fa[fa[y]]=fa[x]\n",
    "            fa[y]=fa[x]\n",
    "        for num in nums:\n",
    "            i=2\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    find(num)\n",
    "                    find(i)\n",
    "                    unionf(num, i)\n",
    "                    find(num // i)\n",
    "                    unionf(num, num // i)\n",
    "                i += 1\n",
    "        return max(Counter(find(num) for num in nums).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        maxnum=max(nums)+1\n",
    "        n=len(nums)\n",
    "        fa=[0]*maxnum\n",
    "        for i in range(maxnum):\n",
    "            fa[i]=i\n",
    "        def find(x):\n",
    "            nonlocal fa\n",
    "            if x==fa[x]:\n",
    "                return x\n",
    "            fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        def unionf(x,y):\n",
    "            nonlocal fa\n",
    "            fa[fa[y]]=fa[x]\n",
    "            fa[y]=fa[x]\n",
    "        for num in nums:\n",
    "            i=2\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    if find(num)!=find(i):\n",
    "                        unionf(num, i)\n",
    "                    if find(num)!=find(num // i):\n",
    "                        unionf(num, num // i)\n",
    "                i += 1\n",
    "        return max(Counter(find(num) for num in nums).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "\n",
    "        N=max(nums)+1\n",
    "        parent=list(range(N))\n",
    "        def find(x):\n",
    "            if x!=parent[x]:\n",
    "                parent[x]=find(parent[x])\n",
    "            return parent[x]\n",
    "        def union(x,y):\n",
    "            a,b=find(x),find(y)\n",
    "            if a!=b:\n",
    "                parent[b]=a\n",
    "        \n",
    "        st=set(nums)\n",
    "        for i in range(2,N):\n",
    "            for j in range(i,N,i):\n",
    "                if j in st:\n",
    "                    union(i,j)\n",
    "\n",
    "        cnt=Counter()\n",
    "        res=1\n",
    "        for v in st:\n",
    "            cnt[find(v)]+=1\n",
    "            res=max(res,cnt[find(v)])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        #n=len(nums)\n",
    "        m=max(nums)\n",
    "        father=[0]*(m+1)\n",
    "        for i in range(m+1):\n",
    "            father[i]=i\n",
    "        def find(x):\n",
    "            if father[x]==x:\n",
    "                return x\n",
    "            father[x]=find(father[x])\n",
    "            return father[x]\n",
    "        def union(a,b):\n",
    "            if find(a)!=find(b):\n",
    "                father[find(a)]=find(b)\n",
    "        for num in nums:\n",
    "            i=2\n",
    "            #print(num,i)\n",
    "            while i*i<=num:\n",
    "                if num%i==0:\n",
    "                    #print(num,i)\n",
    "                    union(num,i)\n",
    "                    union(num,num//i)\n",
    "                i+=1\n",
    "        c=collections.Counter()\n",
    "       # print(father)\n",
    "        for num in nums:\n",
    "            #print(num,find(num))\n",
    "            c[find(num)]+=1\n",
    "        ans=-1\n",
    "        for key in c:\n",
    "            if c[key]>ans:\n",
    "                ans=c[key]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        def find(x):\n",
    "            if x != p[x]:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        \n",
    "        n = len(nums)\n",
    "        p = [i for i in range(max(nums)+1)]\n",
    "        for num in nums:\n",
    "            i = 2\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    p[find(num)] = find(i)\n",
    "                    p[find(num)] = find(num // i)\n",
    "                i += 1\n",
    "        \n",
    "        cnt = defaultdict(int)\n",
    "        for num in nums:\n",
    "            cnt[find(num)] += 1\n",
    "        return max(cnt.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        m=max(nums)\n",
    "        father=[0]*(m+1)\n",
    "        for i in range(m+1):\n",
    "            father[i]=i\n",
    "        def find(x):\n",
    "            if father[x]==x:\n",
    "                return x\n",
    "            father[x]=find(father[x])\n",
    "            return father[x]\n",
    "        def union(a,b):\n",
    "            if find(a)!=find(b):\n",
    "                father[find(a)]=find(b)\n",
    "        for num in nums:\n",
    "            i=2\n",
    "            #print(num,i)\n",
    "            while i*i<=num:\n",
    "                if num%i==0:\n",
    "                    print(num,i)\n",
    "                    union(num,i)\n",
    "                    union(num,num//i)\n",
    "                i+=1\n",
    "        c=collections.Counter()\n",
    "       # print(father)\n",
    "        for num in nums:\n",
    "            #print(num,find(num))\n",
    "            c[find(num)]+=1\n",
    "        ans=-1\n",
    "        for key in c:\n",
    "            if c[key]>ans:\n",
    "                ans=c[key]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "        root_list = list(range(max(nums) + 1))\n",
    "        rank_list = [0] * (max(nums) + 1)\n",
    "\n",
    "        def find_root(v):\n",
    "            if root_list[v] != v:\n",
    "                root_list[v] = find_root(root_list[v])\n",
    "            return root_list[v]\n",
    "\n",
    "        def add(v, v_up):\n",
    "            v_root = find_root(v)\n",
    "            v_up_root = find_root(v_up)\n",
    "            if v_root == v_up_root:\n",
    "                return\n",
    "            if rank_list[v_root] > rank_list[v_up_root]:\n",
    "                root_list[v_up_root] = v_root\n",
    "            elif rank_list[v_root] < rank_list[v_up_root]:\n",
    "                root_list[v_root] = v_up_root\n",
    "            else:\n",
    "                root_list[v_up_root] = v_root\n",
    "                rank_list[v_root] += 1\n",
    "\n",
    "        for num in nums:\n",
    "            i = 2\n",
    "            while i * i <= num:\n",
    "                if num % i == 0:\n",
    "                    add(num, i)\n",
    "                    add(num, num // i)\n",
    "                i += 1\n",
    "\n",
    "\n",
    "        count_set = {}\n",
    "        for num in nums:\n",
    "            if find_root(num) not in count_set:\n",
    "                count_set[find_root(num)] = 0\n",
    "            count_set[find_root(num)] += 1\n",
    "        result = 0\n",
    "        for v in count_set:\n",
    "            result = max(result, count_set[v])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "graph = defaultdict(list)\n",
    "for i in range(2,10**5+1):\n",
    "    for j in range(2*i,10**5+1,i):\n",
    "        graph[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "\n",
    "        parents = list(range(10**5 + 1))\n",
    "\n",
    "        def find(x):\n",
    "            if x != parents[x]:\n",
    "                parents[x] = find(parents[x])\n",
    "            return parents[x]\n",
    "\n",
    "        def union(u,v):\n",
    "            x , y = find(u) , find(v)\n",
    "            if x != y:\n",
    "                parents[x] = y\n",
    "\n",
    "        for num in nums:\n",
    "            for x in graph[num]:\n",
    "                union(num,x)\n",
    "        \n",
    "        nums = [find(num) for num in nums]\n",
    "\n",
    "        cnts = Counter(nums)\n",
    "        return max(cnts.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestComponentSize(self, nums: List[int]) -> int:\n",
    "\n",
    "        N=10**5+1\n",
    "        parent=list(range(N))\n",
    "        def find(x):\n",
    "            if x!=parent[x]:\n",
    "                parent[x]=find(parent[x])\n",
    "            return parent[x]\n",
    "        def union(x,y):\n",
    "            a,b=find(x),find(y)\n",
    "            if a!=b:\n",
    "                if size[a]>size[b]:\n",
    "                    parent[b]=a\n",
    "                    size[a]+=size[b]\n",
    "                else:\n",
    "                    parent[a]=b\n",
    "                    size[b]+=size[a]\n",
    "        \n",
    "        st=set(nums)\n",
    "        flag=[1]*N\n",
    "        vis=set()\n",
    "        size=[0]*N\n",
    "        for v in st:\n",
    "            size[v]=1\n",
    "\n",
    "        for i in range(2,N):\n",
    "            for j in range(i,N,i):\n",
    "                if j in st:\n",
    "                    union(i,j)\n",
    "        res=1\n",
    "        for v in st:\n",
    "            res=max(res,size[find(v)])\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
